#include<bits/stdc++.h>
using namespace std;
int *kmp_next(char* s1,char *s){
    int n = strlen(s1);
    int next[n+1];
    for(int i=1;i<=n;i++){
        if(i==1){
            next[i] = 0;
        }else if(i>1){
            int j,k;
            for(j=2;j<i;j++){
                for(k=1;k<=j-1;k++){
                    if(next[k]!=next[j-k+1]){
                        break;
                    }
                }
            }
            next[i] = k;
        }
    }
    return next;
}

int kmp(char *st,char *s){
    int* next;//虽然我们知道这个数组占据多少，但是用堆最好
    next = kmp_next(st,s);
    int j=0,i=0;
    while(i<strlen(s)){
        if(st[j]==s[i]){
            j++;i++;
        }else{
            j = next[j];
        }
    }
}
